/**
 * 采用分治和递归的思想，选择一个基数，将小于基数的全部放到左边，反之放到右边，递归执行
*/
class Random {
  randomNum() {
    return Math.random()
  }

  randomArr() {
    return Array.from(new Array(~~(this.randomNum() * 10)).fill(0)).map(num => {
      num = ~~(this.randomNum() * 100)
      return num
    })
  }
}

const quickSort = arr => {
  if (arr.length <= 1) return arr
  const mid = ~~(arr.length / 2),
    povid = arr[mid],
    left = arr.filter((item, index) => {
      if (index !== mid) {
        return item <= povid
      }
    }),
    right = arr.filter(item => item > povid)
  return [...quickSort(left), povid, ...quickSort(right)]
}

const random = new Random()
const arr = random.randomArr()

console.log(quickSort(arr))